// hard

const { ListNode, LinkedList } = require("../../1. 链表基础/1. 建立线性链表");

// 给你链表的头节点head，再给点一个正整数k，k的值小于或等于链表的长度
// 每k个节点一组进行翻转，并返回修改后的链表，如果链表节点总数不是k的整数倍，则将最后剩余的节点保持原有顺序

function reverseKGroup(head, k) {
    // 构造哑结点，第一个节点可能需要反转
    let dummy_head = new ListNode(0)
    dummy_head.next = head
    // 分别表示链表中待反转区间的首尾节点
    let cur = dummy_head
    let tail = dummy_head.next
    // 当前元素的序号
    let index = 0
    while (tail) {
        index += 1
        if (index % k === 0) {
            cur = reverse(cur, tail.next)
            tail = cur.next
        } else {
            tail = tail.next
        }
    }
    return dummy_head.next
}

function reverse(head, tail) {
    // head代表当前反转区间的第一个节点的前一个节点
    // tail代表当前待反转区间的最后一个节点的后一个节点
    let pre = head
    let cur = pre.next
    // 记录待反转区间的第一个节点，反转之后为尾结点，方便之后进行连接
    let first = cur
    while (cur !== tail) {
        // 保存当前节点的后一个节点
        let next = cur.next
        // 断开当前节点的后一个节点，将curr.next指向上一个节点
        cur.next = pre
        // pre向前移动一步，移动到curr的位置
        pre = cur
        // cur向前移动一步，移动到next保存的位置
        cur = next
    }
    // 待反转区间第一个节点之前的节点指向 反转区间后的头节点
    head.next = pre
    // 待反转区间的第一个节点（反转之后为尾结点）指向待反转区间的最后一个节点的后一个节点
    first.next = tail
    return first
}

let head = [1, 2, 3, 4, 5,6,7], k = 3
let node = new LinkedList(head)
let res = reverseKGroup(node.head, k)
console.log(res);